package com.leetcode.算法策略相关.回溯;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/1/26
 * @description: 51. N 皇后
 * https://leetcode-cn.com/problems/n-queens/
 */
public class C_51_N皇后 {

	static C_51_N皇后 action = new C_51_N皇后();

	public static void main(String[] args) {
//		test1();
		test2();
	}


	public static void test1() {
		int n = 5;
		List<List<String>> lists = action.solveNQueens(n);
		System.out.println("lists = " + lists);
	}

	public static void test2() {
		int n = 1;
		List<List<String>> lists = action.solveNQueens(n);
		System.out.println("lists = " + lists);
	}

	/**
	 * 回溯算法
	 * 1.使用一个二位数组来表示棋谱。
	 * 2.使用一个栈来进行检验
	 * --
	 *
	 * @param n
	 * @return
	 */
	public List<List<String>> solveNQueensFail(int n) {
		List<List<String>> res = new ArrayList<>();
		if (n == 1) {
			res.add(Arrays.asList("Q"));
			return res;
		}
		Stack<int[]> stack = new Stack<>();
		//初始化棋盘
		int[][] chess = new int[n][n];
		for (int i = 0; i < n; i++) {
			stack.push(chess[i]);
			//开始进行回溯
			while (!stack.isEmpty()) {
				//弹出栈顶元素
				int[] curLoc = stack.pop();
				//根据 curLoc 设置 chess 中可以放置的元素
				setLocation(curLoc, chess, n);
			}
		}
		return res;
	}

	/**
	 * 设置 curLoc 位置辐射的位置的值+1
	 * 这里实在是太麻烦了。。。
	 * --
	 * 感觉思路不太对。
	 * 应该还有可以优化的地方
	 * --
	 * 反向思考：如果从正向，要将所有的点都补齐就太麻烦了，老实人的做法！
	 * 反之，如果直接判断是否踩雷，只需要根据之前的位置进行判断即可，会比较节约！
	 * 利用【斜率】的方式方便判断！
	 *
	 * @param curLoc
	 * @param chess
	 * @param n
	 */
	private void setLocation(int[] curLoc, int[][] chess, int n) {
		int i = curLoc[0];
		int j = curLoc[1];
		//求出最小值
		int interval2zero = Math.min(i, j);
		int interval2len = i + j - interval2zero;

		int imin = i - interval2zero;
		int jmin = j - interval2zero;


		//1.处理写着


		//1.将本行 +1
//		for (int j = 0; j < n; j++) {
//			chess[i][j]++;
//		}
		//2.将本列 +1

		for (int k = j; k < n; k++) {
			chess[k][j]++;
		}

		//3.将下行
//		for (i++; i < n; i++) {
//			for (int j = 0; j < n; j++) {
//
//			}
//		}


	}


	/**
	 * 用我自己的想法通过了，虽然才打败了 10%..
	 * 感觉还原上一步比较绕！
	 * @param n
	 * @return
	 */
	public List<List<String>> solveNQueens(int n) {
		List<List<String>> res = new ArrayList<>();
		//使用一个 linkedList 来保存落子的情况
		LinkedList<int[]> linkedList = new LinkedList<>();
		int endIndex = n - 1;
		for (int i = 0; i < n; i++) {
			//在行间遍历，每多一行，就说明离结果越近
 			for (int j = 0; j < n; j++) {
				//在列间遍历，每多一行，说明失败就多一次
				if (checkPosition(i, j, linkedList)) {
					//如果在 i,j 的地方落子是安全的
					linkedList.add(new int[]{i, j});
					if (linkedList.size() == n) {
						//说明已经走完
						res.add(getChess(linkedList, n));
						//回撤，返回上一行
						linkedList.removeLast();

						int[] tempArr = null;
						while (!linkedList.isEmpty()){
							tempArr = linkedList.removeLast();
							if (tempArr[1] != endIndex){
								break;
							}
							//此时列已经遍历完毕

						}
						//防止 n = 1 时的异常
						if (tempArr == null||(linkedList.isEmpty() && tempArr[1] == endIndex)){
							break;
						}
						j = tempArr[1];
						i = tempArr[0];
						continue;
					}

					//不继续在 列间 尝试，而是直接去下一行
					break;
				} else {
					//如果 此处落子不安全，那么剪枝，继续尝试下一列
					if (j == endIndex) {
						//如果已经遍历到 列末 了
						//进行回撤 上一行的数据，继续在上一行进行遍历
						//linkedList.removeLast();
						//回撤行
						int[] tempArr = null;
						while (!linkedList.isEmpty()){
							tempArr = linkedList.removeLast();
							if (tempArr[1] != endIndex){
								break;
							}
							//此时列已经遍历完毕
						}
						//防止 n = 1 时的异常
						if (tempArr == null||(linkedList.isEmpty() && tempArr[1] == endIndex)){
							break;
						}
						j = tempArr[1];
						i = tempArr[0];
					}
				}
			}
//			if (i == -1) {
//				//完成整个回溯的过程
//				break;
//			}
		}
		return res;
	}

	/**
	 * 检查 i 行 j 列的数据是否与 deque 中有冲突
	 *
	 * @param i
	 * @param j
	 * @param list
	 * @return
	 */
	private boolean checkPosition(int i, int j, LinkedList<int[]> list) {
		if (list.isEmpty()) {
			return true;
		}
		Iterator<int[]> iterator = list.iterator();
		while (iterator.hasNext()) {
			int[] arr = iterator.next();
			if (arr[1] == j) {
				return false;
			}
			if (arr[0] - i == arr[1] - j || arr[0] - i == j - arr[1]) {
				return false;
			}
		}

		return true;
	}

	/**
	 * 形成棋子
	 *
	 * @param deque
	 * @param n
	 * @return
	 */
	private List<String> getChess(LinkedList<int[]> deque, int n) {
		List<String> res = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			int[] arr = deque.removeFirst();
			char[] chars = new char[n];
			for (int j = 0; j < n; j++) {
				if (j == arr[1]) {
					chars[j] = 'Q';
				} else {
					chars[j] = '.';
				}
			}
			res.add(new String(chars));
			//继续塞到末尾，以供下次回溯
			deque.addLast(arr);
		}
		return res;
	}

}
